package DataStructure.graph;

import DataStructure.linear.Queue;
import DataStructure.priority.IndexMinPriorityQueue;

public class DijkstraSP {
    //索引代表顶点，值表示从顶点s到当前顶点的最短路径上的最后一条边
    private DirectedEdge[] edgeTo;
    //索引代表顶点，值从顶点s到当前顶点的最短路径的总权重
    public double[] distTo;
    //存放树中顶点与非树中顶点之间的有效横切边
    private IndexMinPriorityQueue<Double> pq;

    //根据有向加权图G和s顶点，创建一个计算顶点为s的最短路径树对象
    public DijkstraSP(EdgeWeightedDigraph G,int s){
        this.edgeTo=new DirectedEdge[G.V()];
        this.distTo=new double[G.V()];
        for (int i = 0; i < distTo.length; i++) {
            distTo[i]=Double.POSITIVE_INFINITY;
        }
        this.pq=new IndexMinPriorityQueue<>(G.V());
        //找到图G中以顶点s为起点的最短路径树
        //默认让顶点s进入到最短路径树中
        distTo[s]=0.0;
        pq.insert(s,0.0);
        //遍历pq
        while (!pq.isEmpty()){
            relax(G,pq.delMin());
        }
    }

    //松弛图G中顶点v
    public void relax(EdgeWeightedDigraph G,int v){
        for (DirectedEdge edge : G.adj(v)) {
            //获取该边的终点w
            int w = edge.to();
            //通过松弛技术判断从s到w的最短路径是否需要先从s到v,再从v到w
            if(distTo[v]+edge.weight()<distTo[w]){
                distTo[w]=distTo[v]+edge.weight();
                edgeTo[w]=edge;
                //判断pq中是否已经存在w，如果存在，则更新权重，如果不存在，则添加
                if(pq.contains(w)){
                    pq.changeItem(w,distTo[w]);
                }else {
                    pq.insert(w,distTo[w]);
                }
            }
        }
    }

    //获取顶点s到v的最短路径的总权重
    public double disTo(int v){
        return distTo[v];
    }

    //判断从s到v是否可以达到
    public boolean hasPathTo(int v){
        return distTo[v]<Double.POSITIVE_INFINITY;
    }

    //查询从s到v的最短路径的所有边
    public Queue<DirectedEdge> pathTo(int v){
        //判断s到v是否可达
        if(!hasPathTo(v)){
            return null;
        }
        //创建一个队列对象
        Queue<DirectedEdge> allEdges = new Queue<>();
        while (true){
            DirectedEdge e = edgeTo[v];
            if(e==null){
                break;
            }
            allEdges.enqueue(e);
            v=e.from();
        }
        return allEdges;
    }
}
